package org.usmile.algorithms.leetcode.middle;

/**
 * 421. 数组中两个数的最大异或值
 *
 * 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
 *
 * 示例 1：
 * 输入：nums = [3,10,5,25,2,8]
 * 输出：28
 * 解释：最大运算结果是 5 XOR 25 = 28.
 *
 * 示例 2：
 * 输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
 * 输出：127
 *
 * 提示：
 * 1 <= nums.length <= 2 * 105
 * 0 <= nums[i] <= 231 - 1
 */
public class _0421 {
}

class _0421_Solution {
    public int findMaximumXOR(int[] nums) {
        Trie trie = new Trie();
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            trie.add(nums[i - 1]);
            res = Math.max(res, trie.maxXor(nums[i]));
        }
        return res;
    }

    private static class Trie {
        private static class Node {
            Node zero;
            Node one;

            Node() {}
        }

        private final Node root;
        public Trie() {
            root = new Node();
        }

        // 将 num 的二进制从高位到低位添加到前缀树中
        public void add(int num) {
            Node curr = root;
            // 整数的最高一位是符号位，对于正数的话是 0
            //      0100 0000 0000 0000 0000 0000 0000 0000 >> 30
            // ->   0000 0000 0000 0000 0000 0000 0000 0001
            // & 1  0000 0000 0000 0000 0000 0000 0000 0001
            // bug 修复，是 k--
            for (int k = 30; k >= 0 ; k--) {
                int bit = (num >> k) & 1;
                if (bit == 0) {
                    if (curr.zero == null) {
                        curr.zero = new Node();
                    }
                    curr = curr.zero;
                } else {
                    if (curr.one == null) {
                        curr.one = new Node();
                    }
                    curr = curr.one;
                }
            }
        }

        // 在前缀树中查找和 num 进行异或，得到的最大的异或值
        public int maxXor(int num) {
            Node curr = root;
            int x = 0;
            // bug 修复，是 k--
            for (int k = 30; k >= 0; k--) {
                int bit = (num >> k) & 1;
                if (bit == 0) {
                    if (curr.one != null) {
                        curr = curr.one;
                        x = 2 * x + 1;
                    } else {
                        curr = curr.zero;
                        x = 2 * x;
                    }
                } else {
                    if (curr.zero != null) {
                        curr = curr.zero;
                        x = 2 * x + 1;
                    } else {
                        curr = curr.one;
                        x = 2 * x;
                    }
                }
            }

            return x;
        }
    }
}